//
// Created by 党清浩 on 2021/11/4.
//

#include <stdio.h>
#include <malloc.h>
typedef char DataType;
/*定义二叉树*/
typedef struct Node {
    DataType data;
    struct Node *LChild;
    struct Node *RChild;
} BiTNode, *BiTree;

/*扩展先序遍历序列创建二叉链表*/
void CreateBiTree(BiTree *bt);

/*先序遍历求二叉树高度*/
void PreTreeDepth(BiTree bt, int h);

/*后序遍历求二叉树高度*/
int PostTreeDepth(BiTree bt);

/*按树状打印二叉树*/
void PrintTree(BiTree bt, int nLayer);

/*统计叶子节点数量*/
int leaf(BiTree bt);

int main() {
    BiTree bt;
    CreateBiTree(&bt);
    printf("The BinaryTree is:\n");
    PrintTree(bt,1);
    printf("\nThe Number of Leaf:%d", leaf(bt));
    printf("\nThe Height of BinaryTree:%d", PostTreeDepth(bt));
    return 0;
}

/*扩展先序遍历序列创建二叉链表*/
void CreateBiTree(BiTree *bt) {
    char ch;
    ch = getchar();
    if (ch == '.') {
        *bt = NULL;
    } else {
        *bt = (BiTree) malloc(sizeof(BiTree));
        (*bt)->data = ch;
        CreateBiTree(&((*bt)->LChild));
        CreateBiTree(&((*bt)->RChild));
    }
}

void PreTreeDepth(BiTree bt, int h) {
    int depth;
    if (bt != NULL) {
        if (h > depth)
            depth = h;
        PreTreeDepth(bt->LChild, h + 1);
        PreTreeDepth(bt->RChild, h + 1);
    }
}

int PostTreeDepth(BiTree bt) {
    int hl, hr, max;
    if (bt != NULL) {
        hl = PostTreeDepth(bt->LChild);
        hr = PostTreeDepth(bt->RChild);
        max = hl > hr ? hl : hr;
        return (max + 1);
    } else return 0;
}

int leaf(BiTree root) {
    int LeafCount;
    if(root==NULL)
        LeafCount=0;
    else if((root->LChild==NULL)&&(root->RChild==NULL))
        LeafCount=1;
    else
        LeafCount= leaf(root->LChild)+ leaf(root->RChild);
    return LeafCount;
}

void PrintTree(BiTree bt, int nLayer) {
    int i;
    if (bt == NULL)
        return;
    PrintTree(bt->RChild, nLayer + 1);
    for (i=0;i<nLayer;i++){
        printf("%-3s"," ");
    }
    printf("%c\n", bt->data);
    PrintTree(bt->LChild, nLayer + 1);

}